A neural-network architecture for competitive assignment requires that elements of two sets (e.g., resources and targets) be associated with each other so as to minimize the total cost of the associations. It is assumed that all pairwise costs of associating an element of one set with an element of the others are given. Such an assignment is a class of global optimization problems that pose a computational bottleneck in a number of computation-intensive real-time systems. In the assignment paradigm, members of one set {R.sub.i :1.ltoreq.i.ltoreq.M} (e.g., resources) are to be assigned to members of another set {C.sub.j :1.ltoreq.j.ltoreq.N} (e.g., consumers or targets). An assignment is denoted by a binary matrix X={x.sub.ij }, where x.sub.ij =1 if R.sub.i is associated with C.sub.j and x.sub.ij =0 otherwise. The total cost of a selected assignment is given by ##EQU1## where W.sub.ij is the pairwise assignment cost matrix. Assignments are not arbitrary; "blocking" constraints specifying the number of elements of {C.sub.j } that may be associated with each element R.sub.i, and the number of elements of {R.sub.i } that may be associated with each C.sub.j are given as well. While one-to-one blocking constraints are most commonly encountered, some applications require one-to-several or several-to-several associations. Thus, the assignment problem is to choose an assignment X that minimizes COST.sub.TOTAL (X) and satisfies the blocking constraints.
From a circuit implementation standpoint, the traditional additive neural network for assignment requires a two-dimensional matrix of neurons referred to hereinafter as processing units, PUs, and therefore the connection matrix requires a third dimension. As current VLSI technology is essentially two-dimensional, only small additive networks may be implemented on standard die sizes, and even nonstandard technologies such as wafer-scale implementations and chip stacking may limit N and M to a hundred or so. Larger problem sizes require a reformulation of the network model to reduce connectivity. The new architecture presented below has only a few times more connections than PUs and is compatible with VLSI implementation. Means have been developed for applying association costs, satisfying blocking constraints, forcing PUs to hypercube corners and implementing annealing.
A constraint on the number of elements of {R.sub.i } that may be associated with C.sub.j is equivalent to a constraint on the number of activated PUs in column j of the PU matrix. Similarly, constraints on the number of elements of {C.sub.j } associated with R.sub.i specify how many PUs may be on in row i. Focusing on a single row, a circuit that forces only one neuron to turn on, thus enforcing a one-to-one assignment, is the winner-take-all (WTA). The WTA, via mutual inhibition, allows only the PU with the maximum input excitation to become activated; all other PUs are turned off. The WTA model has been extended to allow multiple winners in the k-WTA formulation of Majani, et al., "On the k-winners-take-all network," Advances in Neural Information Systems 1, D. Touretzky, ed., pp. 634-642, Palo Alto, Calif., Morgan Kaufman Publishers, Inc. (1989).
While the k-WTA would allow each R.sub.i and C.sub.j to be associated with a programmable number k.sub.i.sup.R or k.sub.j.sup.c of elements of the other set, the new architecture presented below has generalized the method one step further to allow elements to be independently associated with a range or window of elements of the other set. The resulting function, the k,m-WTA, uses the variable pair (k,m) to specify the minimum and maximum number of associated elements. By setting k=m, the k-WTA one-to-several association function is obtained, and by setting k=m=1, one-to-one association may be specified. obtained, and by setting k=m=1, one-to-one association may be specified.
Each row and each column is connected using the k,m-WTA. The question whether these multiply overlapping winner-take-all circuits can still function correctly was addressed by Brown and Liu, "Neural network design of a Banyan network controller," IEEE Journal of Selected Areas in Communication, Vol. 8, No. 8, pp. 1428-1438, (1991), who found that WTA and k-WTA circuits still function correctly when overlapped arbitrarily. Note, however, that it is possible to specify inconsistent blocking constraints which cannot all be satisfied simultaneously. Letting (k.sub.i.sup.R,m.sub.i.sup.R) and (k.sub.j.sup.c,m.sub.j.sup.c) be the row and column constraints (MIN,MAX), respectively, a necessary condition for consistency is ##EQU2##
The association costs W.sub.ij are distributed throughout the interconnection matrix. A key to the present assignment architecture is that association costs are subtracted locally from the input PUs representing the assignments, Moopenn, et al., "A neural network for euclidian distance minimization," Proc. IEEE, Intl. Conf. on Neural Networks, Vol. II, pp. 349-356, San Diego, Calif., Jul. 24-27, (1988). This tends to inhibit PUs with a high association cost while pushing PUs with low energy costs towards activation. Consequently, low-cost assignment configurations are favored by the k,m-WTA circuits. processor can be designed with connections only along rows and columns of a matrix of PUs (to implement the k,m-WTA) and a few global connections to all PUs.
The complexity of the assignment problem may be understood by considering that for sets of N and M elements, the number of possible solutions satisfying one-to-one (and in some cases one-to-zero) blocking constraints is N!/(N-M)!, assuming NaM. Because the problem requires a global solution, it cannot be decomposed without risk of losing the optimal solution. Nevertheless, when fast solutions are required, the problem is generally solved either by decomposition or limited best-fit search. Search algorithms that find optimal solutions include Munkres' method which has a computational complexity of O(MN.sup.2). See J. Munkres, "Algorithms for the assignment and transportation problems," Journal of the Society for Industrial Applications, of Mathematics, Vol. 5, No. 1, pp. 32-38, (1957) and S. Blackman, Multiple-Target Tracking with Radar Applications, Artech House Inc., Norwood, Mass., pp. 397-403, (1986). While more efficient than exhaustive enumeration, such algorithms remain computation-intensive, requiring seconds or minutes of processing on powerful computers. These methods are therefore not suitable for many real-time applications. Furthermore, for problems with one-to-several and several-to-several blocking constraints, the number of possible solutions can be considerably larger and no known efficient search algorithms exist. Practical applications that fit into this assignment paradigm are detailed below.
In the military domain, an obvious and time-honored application is weapon-target association. Of particular importance is neutralization of intelligent missiles, which have attained a position of primary importance among munitions in today's military defense tactics. In many cases, the time between threat detection and countermeasure deployment is on the order of seconds, so the automated detection and decision-making components of a defense system must be highly optimized for speed, especially if humans are in the loop as well. In an idealized situation, the various threats are identified and the most appropriate countermeasures applied. Indeed, it may be necessary to allocate several disparate countermeasures to the more serious threats, or perhaps in some cases several threats may be dealt with by one defensive system. Consequently, the traditional one-to-one assignment paradigm is no longer adequate.
Another application is radar tracking of aircraft (e.g., at large airports) or missiles (e.g., ICBM tracking as a component of Strategic Defense Initiative systems). In order to track individual objects from a swarm of tens or hundreds, "blips" from successive radar sweeps must be matched. An alternative approach is to use Kalman filters to estimate the bearing and velocity of the individual objects and to assign the instantaneous estimated positions to the actual positions determined by radar.
Finally, an application that is becoming increasingly important as computer and national telecommunication networks convert to the transmission of information (e.g., audio, fax, video) by discrete units of digital data, is high-speed network packet switching. Within a communications network the function of a switching node can be viewed as an assignment of node inputs to node outputs. The blocking constraints require that at any one time each input is assigned to one output vice versa. The switch may have additional constraints if there is no direct path from each input to each output. The cost of assigning an input to an output depends on whether or not the input has data waiting for that output. Cumulative latency time and packet priority may need to be taken into account as well. The assignment paradigm developed in this application is compatible with a switching network having maximal throughput and near-optimal delay.
Traditionally, global optimization problems of this competitive assignment type have been solved by computationally exhaustive searches where the number of computations increases as the cube of the number of resources. The computational load may be reduced by heuristic means, but in that case the solution is not guaranteed to be optimal or even good.
A means for overcoming the limitations in computation speed imposed by serial digital computers is parallel processing, whether digital or analog. One possible method for solving assignment problems is based on massively parallel analog computation using neural networks.
The neural network architecture that has received the most attention for solving optimization problems is the Hopfield network described by Hopfield and Tank, "Neural computation of decisions in optimization problems," Biol. Cybern, 52:147-152, (1985). This architecture, shown in FIG. 1, consists of an array of processing operational amplifiers (called neurons but generally referred to herein as processing units) interconnected fully via a matrix of connecting elements of programmable strength (called synapses). The connection strengths of the synapses are variable and it is these weight variables that determine the behavior of the neural network.
With few exceptions, neural network applications have been mapped onto the additive networks by first formulating a Lyapunov function that has energy minima which correspond to the desired solutions. Typically, this "energy equation" is composed of simple quadratic terms each of which is minimized when a particular application constraint is satisfied. From this equation, the interconnection weight matrix is then derived by a simple transformation. An alternative approach is to use heuristics to implement required constraints directly.
The system must be configured such that only as many PUs can be active in each row or column as allowed by the blocking constraints, and association costs must be incorporated such that as the system settles, or relaxes, the better solutions have a competitive advantage over the other. The PUs apply a nonlinear saturating function to the sum of input signals. When they are allowed to take on an analog range of values, as would generally be the case in hardware implementations, the solution space takes the form of an MN-dimensional hypercube, the corners of which correspond to the assignment decisions. To form a complete, unambiguous solution X, all PUs must relax to saturated "on" and completely "off" states.
This additive network has been used for solving, by computer simulation, the concentrator assignment problem, a one-to-several assignment problem in which multiple elements of the one set (named "sites") are matched with each element of the other set (named "concentrators"), as described by Tagliarini and Page, "A neural-network solution to the concentrator assignment problem," Proc. IEEE Conf. on Neural Information Processing Systems--Natural and Synthetic (1988). One application of this problem is selecting how goods should be distributed from a number of warehouses to a chain of retail outlets scattered in a geographic area encompassing the warehouses, such that total transport distance is minimized. Capacities of the individual concentrators were programmed by allocating k.sub.i additional "slack" neuron rows to the basic assignment matrix. The energy function used was ##EQU3## where k.sub.j gives the maximum number of elements supported by concentrator j. From this Lyapunov function, the required weights for satisfying the blocking and neuron on/off constraints were derived. The association costs were heuristically added to the resulting interconnection matrix. In a series of 100 trials of a small 5.times.12 problem, the network never found the optimal solution, but all solutions were within 0.3% of optimal, and most within 0.01%, so it was concluded that the network effectively rejected poor solutions. While solutions of this quality are quite satisfactory for some applications, the problem size was very small. Of concern is whether more realistic problem sizes would result in solutions as good. Also, consider the connectivity complexity for this architecture. If k.sub.max is the largest expected k.sub.i then the number of connections is O(M.sup.2 (M+k.sub.max).sup.2). Such extensive connectivity would pose serious difficulties for hardware implementations.
"Simulated annealing" is one means to improve the quality of solutions found by such competitive optimization architectures, as described by Kirkpatrick, Gelatt and Vecchi, "Optimization by simulated annealing," Science, Vol. 220, pp. 670-680, (1983). Traditionally, annealing involves injecting uncorrelated noise into each neuron and gradually reducing the level of the noise according to an annealing schedule. This has the effect of exciting the system out of local minima in the energy surface and into deeper minima corresponding to better solutions.
An alternative method of annealing, known as "mean-field annealing" is described by Bilbro, et al., "OPTIMIZATION BY MEAN FIELD ANNEALING" Advances in Neural Information Processing Systems 1, Touretsky, ed., Morgan, Kaufman Publishers, Inc., pp. 91-98 (1989) and is especially appealing for hardware implementations. It can be implemented by gradually increasing the slope of the saturating neuron function in the presence of a small level of fixed noise. Application of that annealing to significantly improve the solutions found by competitive optimization architectures is reported by Peng and Reggia, "A connectionist model for diagnostic problem solving," IEEE Trans. on Systems, Man and Cybernetics, Vol. 19, No. 2, pp. 285-289, (1989).
Initially, a method for "resettling" the network was used in which multiple production operations were performed in order to reduce the probability of obtaining a poor solution. With the incorporation of simulated annealing, the network produced quite good solutions to small-scale problems without resettling.